import java.util.ArrayList;
import java.util.Collections;


public class BoardRanker {
	
	public static Position findGoal (Board b){
		for (int i = 0; i<b.getNumRows(); i++){
			for (int j = 0; j<b.getNumColumns(); j++){
				if (b.getData(i, j)== Board.GOAL){
					return new Position(i,j);					
				}
			}
		}
		return new Position(0,0);
		
	}
	
	public static ArrayList<Position> findGoals (Board b){
		ArrayList<Position> goals = new ArrayList<Position>();
		for (int i = 0; i<b.getNumRows(); i++){
			for (int j = 0; j<b.getNumColumns(); j++){
				if (b.getData(i, j)== Board.GOAL){
					goals.add(new Position(i,j));					
				}
			}
		}
		return goals;
		
	}
	
	private static int minOfList (ArrayList<Integer> l){
		ArrayList<Integer> newlist = l;
		Collections.sort(newlist);
		return newlist.get(0);
		
	}
	
	private static int maxOfList (ArrayList<Integer> l){
		ArrayList<Integer> newlist = l;
		Collections.sort(newlist);
		return newlist.get(newlist.size()-1);
		
	}
	
	public static int [][] distancesToAllTarget (Board b){
		ArrayList <Position> goals = findGoals (b); // list of the goals
		ArrayList<int[][]> arrays = new ArrayList<int[][]>(); // list of the array for each goal
		int [][] result = new int[b.getNumRows()][b.getNumColumns()]; // final array
		for (int a = 0; a < goals.size(); a++){ // construction of the array 
			arrays.add(distancesToOneTarget(goals.get(a), b));
		}
		for (int i = 0; i< b.getNumRows(); i++){
			for (int j = 0; j<b.getNumColumns(); j++){
				ArrayList<Integer> al = new ArrayList<Integer>(); // all the values for i,j
				for (int k = 0; k < goals.size(); k++){ // 
					al.add(arrays.get(k)[i][j]);					
				}
				result[i][j] = maxOfList (al);
			}
		}
		return result;
	}
	
	private static int [][] distancesToOneTarget (Position goal, Board bo){
		
		Board b = BoardRanker.addWall(bo);
//		System.out.println(b.toString());
		//Position goal = findGoal(b);
		
//		ArrayList<int[]> lMovesPlayer = new ArrayList<int[]>(); //
		int[][] distances = new int [b.getNumRows()][b.getNumColumns()];

	
		
		for (int i = 1; i<b.getNumRows()-1;i++){		
			distances[i][0]=1000;
			distances[i][b.getNumColumns()-1]=1000;
			for (int j = 1; j<b.getNumColumns()-1; j++){
				distances[0][j]=1000;
				distances[b.getNumRows()-1][j]=1000;
				distances[i][j] = 1000;
				
				if (b.getData(i, j)!=Board.WALL){
					ArrayList<Position> lLastSquares = new ArrayList<Position>(); //all squares covered
					Position boxPosition = new Position(i,j);
					int distanceToTarget =0;
					while (!boxPosition.isEqual(goal) && distanceToTarget<100){
//						System.out.println(boxPosition.toString());
						lLastSquares.add(new Position(boxPosition)); // add the initial position to the visited position
						int smallerDistance = 10000;
						int effectivMov = -1; //the best move
						if (b.getData(boxPosition.getI()-1, boxPosition.getJ())!=Board.WALL ){
							int x = goal.getI()-(boxPosition.getI()-1);
							int y = goal.getJ()-boxPosition.getJ();
							int dist = x*x+y*y;
							Position ip= new Position(boxPosition.getI()-1, boxPosition.getJ());
							int ind = 0;
							for (int f=0;f<lLastSquares.size();f++){
								if (ip.isEqual(lLastSquares.get(f))){
									ind = f+1;
								}
							}
							dist += ind*10; //number added if the square has already been visited
							if (dist<smallerDistance){
								smallerDistance = dist;
								effectivMov = 0;
							}
						} 
						if  (b.getData(boxPosition.getI()+1, boxPosition.getJ())!=Board.WALL ){
							int x = goal.getI()-(boxPosition.getI()+1);
							int y = goal.getJ()-boxPosition.getJ();
							int dist = x*x+y*y;
							Position ip= new Position(boxPosition.getI()+1, boxPosition.getJ());
							int ind = 0;
							for (int f=0;f<lLastSquares.size();f++){
								if (ip.isEqual(lLastSquares.get(f))){
									ind = f+1;
								}
							}
							dist += ind*10;	
							if (dist<smallerDistance){
								smallerDistance = dist;
								effectivMov = 1;
							}
						} 
						if (b.getData(boxPosition.getI(), boxPosition.getJ()-1)!=Board.WALL){
							int x = goal.getI()-boxPosition.getI();
							int y = goal.getJ()-(boxPosition.getJ()-1);
							int dist = x*x+y*y;
							Position ip= new Position(boxPosition.getI(), boxPosition.getJ()-1);
							int ind = 0;
							for (int f=0;f<lLastSquares.size();f++){
								if (ip.isEqual(lLastSquares.get(f))){
									ind = f+1;
								}
							}
							dist += ind*10;
							if (dist<smallerDistance){
								smallerDistance = dist;
								effectivMov = 2;
							}
						}
						if (b.getData(boxPosition.getI(), boxPosition.getJ()+1)!=Board.WALL){
							int x = goal.getI()-boxPosition.getI();
							int y = goal.getJ()-(boxPosition.getJ()+1);
							int dist = x*x+y*y;
							Position ip= new Position(boxPosition.getI(), boxPosition.getJ()+1);
							int ind = 0;
							for (int f=0;f<lLastSquares.size();f++){
								if (ip.isEqual(lLastSquares.get(f))){
									ind = f+1;
								}
							}
							dist += ind*10;	
							if (dist<smallerDistance){
								smallerDistance = dist;
								effectivMov = 3;
							}
						} 
						
						
			
						if (effectivMov == 0){
							boxPosition.setI(boxPosition.getI()-1);
						}
			
						if (effectivMov == 1){
							boxPosition.setI(boxPosition.getI()+1);
						}
					
			
						if (effectivMov == 2){
							boxPosition.setJ(boxPosition.getJ()-1);
						}
			
						if (effectivMov == 3){
							boxPosition.setJ(boxPosition.getJ()+1);
						}
						
						distanceToTarget++;
	//					System.out.println(effectivMov);
	//					System.out.println(distanceToTarget);
	//					System.out.println(boxPosition.getI() + " " + boxPosition.getJ());
	//			System.out.println(s);
				
	//			lLastSquares.add(new Position (actualPlayer.getX(), actualPlayer.getY()));
				
					}//end of while
			//System.out.println("path before simplification" + s);
			
					distances[i][j] = distanceToTarget;
				}
			}
		}
		
		for (int i = 0; i<b.getNumRows();i++){
			for (int j=0;j<b.getNumColumns();j++){
				//System.out.print(distances[i][j] +" ");
			}
			//System.out.println();
		}
		int [][] dis = changeDistancesRanking(distances, b.getNumRows(), b.getNumColumns());
		//String stri = simplifyPath(simplifyPath(s));
		return dis;
	}// end of function
	
	
	
	private static int [][] changeDistancesRanking ( int[][] a, int row, int column){
		int [][] b = new int [row][column];
		
		//System.out.println("changes n and initial value");
		
		for (int i = 0; i< row ; i++){
			for (int j = 0; j<column; j++){
				int n = 10 - a[i][j];
				//System.out.print(a[i][j] + " " +n + "     ");
				if (n<0) n = 0;
				b[i][j]= (int) Math.pow(2, n);
			}
			//System.out.println();
		}
		return b;
	}
	
	
	
	
	private static Board addWall (Board b){
		Board b2 = new Board (b.getNumRows(), b.getNumColumns());
		for (int i = 0; i<b2.getNumRows(); i++){
			for (int j = 0; j< b2.getNumColumns(); j++){
				b2.setData(i, j, b.getData(i, j));
				b2.setData(i, 0, Board.WALL);
				b2.setData(i, b2.getNumColumns()-1, Board.WALL);
				b2.setData(0, j, Board.WALL);
				b2.setData(b2.getNumRows()-1, j, Board.WALL);
			}
		}
		return b2;
	}

}
